package 数字字符串20250224;

/**
 * 41.缺失的第一个正整数
 * https://leetcode.cn/problems/first-missing-positive/description/
 * @author
 * @version 1.0
 * @className LossMinInt
 * @since 1.0
 */
public class LossMinInt {
    public static void main(String[] args) {
        int[] a = {1,2,0};
        firstMissingPositive(a);
    }
    /**
     * 规定空间复杂度为常数，要么就是只能定义变量，比如双指针，要么就是使用模仿hash表
     * 这里使用数组模仿hash
     * 将每个元素都放在对应的元素减一的数组中
     * 第一个出现的不配对的就是缺失的值
     * @param nums
     * @return
     */
    public static int firstMissingPositive(int[] nums) {
        for(int i=0;i<nums.length;i++){
            //将元素放在对应的位置
            while(nums[i]<nums.length+1&&nums[i]-1!=i&&nums[i]>0){
                if(nums[i]==nums[nums[i]-1]){
                    break;
                }
                //交换,nums[i]应该在nums[nums[i]-1]
                int temp = nums[i];
                nums[i]=nums[temp-1];
                nums[temp-1]=temp;
            }
        }
        //判断到第一个不匹配的值
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]-1!=i){
                return i+1;
            }
        }
        return nums.length+1;
    }
}
